package com.hyb.algorithm.data.struct.backtrack;

import java.util.ArrayList;
import java.util.List;

/**
 * 77. 组合
 * https://leetcode.cn/problems/combinations/description/
 *
 * @author: ybhu
 * @create: 2023/12/28 22:35
 */
public class Combine2 {


    List<List<Integer>> res;
    public List<List<Integer>> combine(int n, int k) {

        res=new ArrayList<List<Integer>>();
        List<Integer> list=new ArrayList<Integer>();
        backTrack(n,k,1,list);
        return res;
    }


    public void backTrack(int n,int k ,int start,List<Integer> list ){

        //递归终止条件  与分割的区别 start=k 而不是 start=n才终止
        if(list.size()==k){
            res.add(new ArrayList<Integer>(list));
            return;
        }

        //优化的地方 ， k 个元素 应该还剩 n-(k-list.size())+1
        for(int i=start;i<=n-(k-list.size())+1;i++){
            list.add(i);
            backTrack(n,k,i+1,list);
            list.remove(list.size()-1);
        }
    }
}
